import java.util.*;

public class Utils
{
    private static final java.util.Random _RAND = new Random();

    public static RectangleR findBox(ArrayList<PointR> points)
    {
        double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
        double maxX = Double.MAX_VALUE, maxY = Double.MIN_VALUE;

        for (PointR p : points)
        {
            if (p.x < minX)
            {
                minX = p.x;
            }

            if (p.x > maxX)
            {
                maxX = p.x;
            }

            if (p.y < minY)
            {
                minY = p.y;
            }

            if (p.y > maxY)
            {
                maxY = p.y;
            }

        }
        return new RectangleR(minX, minY, maxX - minX, maxY - minY);
    }

    public static double distance(PointR p1, PointR p2)
    {
        double dx = p2.x - p1.x;
        double dy = p2.y - p1.y;

        return Math.sqrt(dx * dx + dy * dy);
    }

    public static PointR centroid(ArrayList<PointR> points)
    {
        double xSum = 0.0;
        double ySum = 0.0;

        for (PointR p : points)
        {
            xSum += p.x;
            ySum += p.y;
        }

        return new PointR(xSum / points.size(), ySum / points.size());
    }

    public static double pathLength(ArrayList<PointR> points)
    {
        double length = 0.0;
        for (int i = 1; i < points.size(); ++i)
        {
            try
            {
                length += Utils.distance(points.get(i - 1), points.get(i));
            } catch (java.lang.IndexOutOfBoundsException e)
            {

            }
        }
        return length;
    }

    public static double angleInDegrees(PointR start, PointR end, boolean positive)
    {
        double radians = angleInRadians(start, end, positive);
        return radToDeg(radians);
    }

    public static double angleInRadians(PointR start, PointR end, boolean positive)
    {
        double radians = 0.0;
        if (start.x != end.x)
        {
            radians = Math.atan2(end.y - start.y, end.x - start.x);
        }
        else
        // pure vertical movement
        {
            if (end.y < start.y)
            {
                radians = -1.0 * Math.PI / 2.0; // -90 degrees is straight up
            }
            else if (end.y > start.y)
            {
                radians = Math.PI / 2.0; // 90 degrees is straight down
            }
        }
        if (positive && radians < 0.0)
        {
            radians += Math.PI * 2.0;
        }
        return radians;
    }

    public static double radToDeg(double rad)
    {
        return (rad * 180.0 / Math.PI);
    }

    public static double degToRad(double deg)
    {
        return (deg * Math.PI / 180.0);
    }

    public static ArrayList<PointR> rotateByDegrees(ArrayList<PointR> points, double degrees)
    {
        double radians = degToRad(degrees);
        return rotateByRadians(points, radians);
    }

    public static ArrayList<PointR> rotateByRadians(ArrayList<PointR> points, double radians)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        PointR c = centroid(points);

        double cos = Math.cos(radians);
        double sin = Math.sin(radians);

        double cx = c.x;
        double cy = c.y;

        for (int i = 0; i < points.size(); ++i)
        {
            PointR p = (PointR) points.get(i);

            double dx = p.x - cx;
            double dy = p.y - cy;

            PointR q = new PointR(0, 0);
            q.x = dx * cos - dy * sin + cx;
            q.y = dx * sin + dy * cos + cy;

            newPoints.add(q);
        }
        return newPoints;
    }

    public static PointR rotatePoint(PointR p, PointR c, double radians)
    {
        PointR q = new PointR(0, 0);
        q.x = (p.x - c.x) * Math.cos(radians) - (p.y - c.y) * Math.sin(radians) + c.x;
        q.y = (p.x - c.x) * Math.sin(radians) + (p.y - c.y) * Math.cos(radians) + c.y;
        return q;
    }

    public static ArrayList<PointR> translateBoundBoxTo(ArrayList<PointR> points, PointR toPt)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        RectangleR r = Utils.findBox(points);
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = points.get(i);
            p.x += (toPt.x - r.getX());
            p.y += (toPt.y - r.getY());
            newPoints.add(p);
        }
        return newPoints;
    }

    public static ArrayList<PointR> translateCentroidTo(ArrayList<PointR> points, PointR toPt)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        PointR centroid = centroid(points);
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = (PointR) points.get(i);
            p.x += (toPt.x - centroid.x);
            p.y += (toPt.y - centroid.y);
            newPoints.add(p);
        }
        return newPoints;
    }

    public static ArrayList<PointR> translateBy(ArrayList<PointR> points, SizeR sz)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = (PointR) points.get(i);
            p.x += sz.getWidth();
            p.y += sz.getHeight();
            newPoints.add(p);
        }
        return newPoints;
    }

    public static ArrayList<PointR> scaleToMax(ArrayList<PointR> points, RectangleR box)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        RectangleR r = findBox(points);
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = (PointR) points.get(i);
            p.x *= (box.maxSide() / r.maxSide());
            p.y *= (box.maxSide() / r.maxSide());
            newPoints.add(p);
        }
        return newPoints;
    }

    public static ArrayList<PointR> scaleToMin(ArrayList<PointR> points, RectangleR box)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        RectangleR r = findBox(points);
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = (PointR) points.get(i);
            p.x *= (box.minSide() / r.minSide());
            p.y *= (box.minSide() / r.minSide());
            newPoints.add(p);
        }
        return newPoints;
    }

    public static ArrayList<PointR> resample(ArrayList<PointR> points, int n)
    {
        double i = pathLength(points) / (n - 1); // interval length
        double d = 0.0;
        ArrayList<PointR> srcPts = new ArrayList<PointR>(points);
        ArrayList<PointR> dstPts = new ArrayList<PointR>(n);
        try
        {
            dstPts.add(srcPts.get(0));
        } catch (Throwable e)
        {

        }
        for (int j = 1; j < srcPts.size(); j++)
        {
            PointR pt1 = (PointR) srcPts.get(j - 1);
            PointR pt2 = (PointR) srcPts.get(j);

            double dist = distance(pt1, pt2);
            if ((d + dist) >= i)
            {
                double qx = pt1.x + ((i - d) / dist) * (pt2.x - pt1.x);
                double qy = pt1.y + ((d - d) / dist) * (pt2.y - pt1.y);
                PointR q = new PointR(qx, qy);
                dstPts.add(q); // append new point 'q'
                srcPts.add(j, q); // insert 'q' at position i in points s.t. 'q'
                                  // will be the next i
                d = 0.0;
            }
            else
            {
                d += dist;
            }
        }
        // somtimes we fall a rounding-error short of adding the last point, so
        // add it if so
        if (dstPts.size() == n - 1)
        {
            dstPts.add((PointR) srcPts.get(srcPts.size() - 1));
        }
        return dstPts;
    }

    public static double pathDistance(ArrayList<PointR> path1, ArrayList<PointR> path2)
    {
        double dist = 0;
        for (int i = 0; i < path1.size(); i++)
        {
            dist += distance((PointR) path1.get(i), (PointR) path2.get(i));
        }
        return dist / path1.size();
    }

    public static int random(int low, int high)
    {
        return _RAND.nextInt(high - low + 1) + low;
    }

    public static int[] random(int low, int high, int num)
    {
        int[] array = new int[num];
        for (int i = 0; i < num; i++)
        {
            array[i] = random(low, high);
            for (int j = 0; j < i; j++)
            {
                if (array[i] == array[j])
                {
                    i--;
                    break;
                }
            }
        }
        return array;
    }

    public static ArrayList<PointR> scaleTo(ArrayList<PointR> points, SizeR sz)
    {
        ArrayList<PointR> newPoints = new ArrayList<PointR>(points.size());
        RectangleR r = findBox(points);
        for (int i = 0; i < points.size(); i++)
        {
            PointR p = points.get(i);
            if (r.getWidth() != 0.0)
            {
                p.x *= (sz.getWidth() / r.getWidth());
            }
            if (r.getHeight() != 0.0)
            {
                p.y *= (sz.getHeight() / r.getHeight());
            }
            newPoints.add(p);
        }
        return newPoints;
    }
}
